package com.c2b.algorithm.leetcode.jzoffer;

/**
 * <a href="https://www.nowcoder.com/practice/ef1f53ef31ca408cada5093c8780f44b?tpId=13&&tqId=11166&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking">调整数组顺序使奇数位于偶数前面(一)</a>
 * <p>
 * 输入一个长度为 n 整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前面部分，所有的偶数位于数组的后面部分，
 * 并保证<b>奇数和奇数，偶数和偶数之间的相对位置不变</b>
 * </p>
 * <p>
 * 数据范围：0≤n≤5000，数组中每个数的值 0 ≤ val ≤10000<br>
 * 要求：时间复杂度O(n)，空间复杂度O(n)<br>
 * 进阶：时间复杂度O(n^2)，空间复杂度O(1)<br>
 * </p>
 *
 * @author c2b
 * @since 2023/3/8 16:02
 */
public class JzOffer0021ReOrderArray_S {
    /**
     * 双指针。时间复杂度O(n)，空间复杂度O(n)
     */
    public int[] reOrderArray(int[] array) {
        if (array == null || array.length == 1) {
            return array;
        }
        int[] res = new int[array.length];
        int left = 0;
        int right = array.length - 1;
        for (int i = 0; i < array.length; i++) {
            // 从左往右：奇数
            if (array[i] % 2 == 1) {
                res[left++] = array[i];
            }
            if (array[array.length - 1 - i] % 2 == 0) {
                res[right--] = array[array.length - 1 - i];
            }
        }
        return res;
    }

    /**
     * 进阶：双指针在原数组上修改。时间复杂度O(n)，空间复杂度O(1)
     */
    public int[] reOrderArray2(int[] nums) {
        if (nums == null || nums.length <= 1) {
            return nums;
        }
        int leftIndex = 0;
        int rightIndex = nums.length - 1;
        while (leftIndex < rightIndex) {
            if (nums[leftIndex] % 2 == 1) {
                // 从左往右，恰好为奇数，排序下一个位置的数字
                leftIndex++;
            } else {
                // 从左往右，为偶数。此时需要从右往左找到第一个奇数,找到leftIndex右侧即可
                while (nums[rightIndex] % 2 == 0) {
                    rightIndex--;
                    if (rightIndex <= leftIndex) {
                        return nums;
                    }
                }
                int temp = nums[leftIndex];
                nums[leftIndex] = nums[rightIndex];
                nums[rightIndex] = temp;

            }
        }
        return nums;
    }

    public static void main(String[] args) {
        JzOffer0021ReOrderArray_S jzOffer0021ReOrderArray_ = new JzOffer0021ReOrderArray_S();
        int[] ints = jzOffer0021ReOrderArray_.reOrderArray2(new int[]{2, 4, 6});
        for (int anInt : ints) {
            System.out.println(anInt);
        }
    }
}
